МIНIСТЕРСТВО ОСВIТИ І НАУКИ УКРАЇНИ
Національний унiверситет "Львiвська полiтехнiка"
ПРЯМИЙ МЕТОД ДОСТУПУ ДО ФАЙЛІВ НА ЗОВНІШНІХ ЗАПАМ’ЯТОВУЮЧИХ ПРИСТРОЯХ
МЕТОДИЧНІ ВКАЗІВКИ
до лабораторної роботи N 2
з курсу "Організація баз даних і знань "
для студентiв базового напрямку 6.0804
"Комп’ютернi науки"
Затверджено на засiданнi кафедри Системи автоматизованого проектування"
Протокол N14 вiд 03.04.1997р.
Львiв 2002
ПРЯМИЙ МЕТОД ДОСТУПУ ДО ФАЙЛІВ НА ЗОВНІШНІХ ЗАПАМ’ЯТОВУЮЧИХ ПРИСТРОЯХ: Методичні вказівки до лабораторної роботи N2 з курсу "Організація баз даниз і знань" для студентiв базового напрямку "Комп’ютернi науки" / Укл. А.Б.Керницький, І.І.Мотика, Ю.В.Стех. - Львiв: НУЛП, 2002.-11с.
Укладачi: А.Б.Керницький, маг.техн.наук.
І.І.Мотика, канд.техн.наук,доц.,
Ю.В.Стех, канд.техн.наук, доц.
Вiдповiдальний за випуск С.П.Ткаченко, канд.техн.наук, доц.
Рецензенти: М.Б.Близнюк, канд.техн.наук, доц.
I.I.Чура, канд.техн.наук, доц.
НАВЧАЛЬНЕ ВИДАННЯ
ПРЯМИЙ МЕТОД ДОСТУПУ ДО ФАЙЛІВ НА ЗОВНІШНІХ ЗАПАМ’ЯТОВУЮЧИХ ПРИСТРОЯХ
Методичні вказівки до лабораторної роботи N2 курсу "Організація баз даних і знань" для студентiв базового напрямку "Комп’ютернi науки
Укладачi Керницький Андрій Богданович
Мотика Ігор Іванович
Стех Юрій Васильович
Редактор Черничевич О.
Мета роботи
Розглянути органiзацiю i ведення файлiв прямого доступу; набути практичнi навички у програмуваннi алгоритмiв доступу хешуванням.
2. КОРОТКІ ТЕОРЕТИЧНІ ВІДОМОСТІ
2.1. МЕТОД ПРЯМОГО ДОСТУПУ
Головною особливiстю прямого методу доступу є взаємна однозначна вiдповiднiсть мiж ключем запису i його фiзичною адресою. Фiзичне розмiщення запису визначається безпосередньо iз значення ключа.
Створивши файл прямого доступу i видiливши для нього необхiдну дiлянку пам’ятi, можна вставляти записи у будь-якi мiсця файла. Перевага такого пiдходу над послiдовною органiзацiєю файла полягає у тому, що вдається отримати запис за заданим значенням ключа без попереднього перегляду всiх попереднiх записiв файла.
ЕФЕКТИВНІСТЬ ДОСТУПУ дорiвнює одиницi.
ЕФЕКТИВНІСТЬ ЗБЕРІГАННЯ залежить вiд густини ключiв. Якщо густина низька, пам’ять використовується неефективно, оскiльки резервуються адреси, що вiдповiдають вiдсутнiм ключам. У цьому випадку доцiльно використовувати для органiзацiї файла метод хешування. Пряму адресацiю можна важати частковим випадком методу хешування.
2.2. МЕТОДИ ХЕШУВАННЯ.
На практицi кiлькiсть можливих значень ключiв набагато перевищує кiлькiсть реально присутнiх у будь-який момент значень цього ключа. У цьому випадку пряма адресацiя є невигiдною, оскiльки надто багато пам’ятi резервується для
3
Додаток
ІНДИВІДУАЛЬНЕ ЗАВДАННЯ
1. Написати програму методу прогресуючого переповнення, яка реалiзує такi функцiї:
1. Друк бази даних.
2. Зчитування запису.
3. Введення запису.
4. Видалення запису.
5. Модифiкацiя запису.
6. Вихiд.
2. Написати програму методу зв'язаних блокiв, яка реалiзує такi функцiї:
1. Друк бази даних.
2. Зчитування запису.
3. Введення запису.
4. Видалення запису.
5. Модифiкацiя запису.
6. Вихiд.
3. Написати програму методу зв'язаних записiв, яка реалiзує такi функцiї:
1. Друк бази даних.
2. Зчитування запису.
3. Введення запису.
4. Видалення запису.
5. Модифiкацiя запису.
10
записiв, яких немає i нiколи не буде у файлi. Метод хешування дає змогу уникнути цього i водночас зберегти ефективнiсть, властиву прямiй адресацiї.
На основi iнформацiї про множину фактичних значень ключiв створюється файл прямого доступу з такою кiлькiстю записiв, яка дещо перевищує фактичне значення ключiв. Вибирається функцiя хешування, яка перетворює значення ключа кожного запису в адресу блока у файлi. Зрозумiло, що хеш-функцiя h - це функцiя, яка вiдображає принцип "багато в один".
2.2.1. ПОШУК
Для того щоб...
